Our wonderful workshop director Aditya Sampath turned 18 (or 12, I'm not really sure) yesterday! Since so many people wished him, he decided to buy candy for all his "K" friends. Soon Sampath found a candy store and decided to buy some of his favorite candies for his friends. The store offers N packs of these candies, where pack i contains Ai candies.
Another reason Sampath decided to buy candies is he likes smelling the wrappers once he is done eating them. That's why he decided to buy exactly M packs and present the friends with the candies and keep the packs for his collection. Sampath would also like the total number of candies to be divisible by K so that an equal distribution of candies between friends is possible. Among all possible sets of packs, Sampath would like to buy a set with the smallest possible total number of candies (since he is cheap).
Another reason Sampath decided to buy candies is he likes smelling the wrappers once he is done eating them. That's why he decided to buy exactly M packs and present the friends with the candies and keep the packs for his collection. Sampath would also like the total number of candies to be divisible by K so that an equal distribution of candies between friends is possible. Among all possible sets of packs, Sampath would like to buy a set with the smallest possible total number of candies (since he is cheap).
Input Format
Each test case consists of two lines. The first of them contains three integers N, M and K. The second of them contains N integers Ai.
Sample Input
SAMPLE INPUT #1
5 3 5
1 2 3 4 5
SAMPLE INPUT #2
6 3 4
9 5 1 7 3 7
Output Format For each test case, output just one line containing the smallest possible total number of bought candies, or -1 if it's impossible to buy exactly M packs so that the total number of candies is divisible by K.
Sample Output
SAMPLE OUTPUT #1
10
SAMPLE OUTPUT #2
-1You must be logged in to submit a solution.